package leetcode.problems;

import org.junit.Test;

import java.util.Arrays;

/**
 * Created by gmwang on 2020/2/1
 * Convert Sorted Array to Binary Search Tree
 * 排序数组转换为二叉搜索树
 */
public class ConvertSortedArrayToBinarySearchTree {
    /**
     * Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
     * 给定一个数组元素按升序排序,将它转换成一个高度平衡BST。
     * For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
     * 对于这个问题,一个高度平衡二叉树的定义是一棵二叉树中,每个节点的两个子树的深度不会相差超过1。
     * Example:
     *
     * Given the sorted array: [-10,-3,0,5,9],
     *
     * One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     *
     *      0
     *     / \
     *   -3   5
     *   /     \
     * -10      9
     **/
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0){
            return null;
        }
        int mid = nums.length / 2;
        TreeNode root = new TreeNode(nums[mid]);
        if(mid == 0) {
            return root;
        }
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        root.left = sortedArrayToBST(left);
        if(mid == nums.length - 1) {
            return root;
        }
        int[] right = Arrays.copyOfRange(nums, mid+1, nums.length);
        root.right = sortedArrayToBST(right);
        return root;
    }


    @Test
    public void test() {
        int [] array = {-10,-3,0,5,9};
        TreeNode res = sortedArrayToBST(array);
        System.out.println(res);
    }

}

